﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace SudokuGame.Sudoku
{
    /// <summary>
    /// 递归回溯算法
    /// </summary>
    public class SudokuSolver
    {
        public SudokuCell[,] SolveSudoku(SudokuCell[,] board)
        {
            var solution = new SudokuCell[board.GetLength(0), board.GetLength(1)];
            Array.Copy(board, solution, board.Length);
            if (BacktrackSolve(solution))
            {
                return solution;
            }
            else
            {
                // 没有找到解
                return null;
            }
        }

        private bool BacktrackSolve(SudokuCell[,] board)
        {
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                {
                    if (board[row, col].Number == 0)
                    {
                        for (int num = 1; num <= 9; num++)
                        {
                            if (IsValid(board, row, col, num))
                            {
                                board[row, col].Number = num;

                                if (BacktrackSolve(board))
                                {
                                    return true;
                                }

                                board[row, col].Number = 0; // 回溯
                            }
                        }

                        return false; // 所有数字都尝试过，没有找到合适的解
                    }
                }
            }

            return true; // 数独已经填满，找到解
        }

        private bool IsValid(SudokuCell[,] board, int row, int col, int num)
        {
            // 检查同行是否有重复数字
            for (int i = 0; i < 9; i++)
            {
                if (board[row, i].Number == num)
                {
                    return false;
                }
            }

            // 检查同列是否有重复数字
            for (int i = 0; i < 9; i++)
            {
                if (board[i, col].Number == num)
                {
                    return false;
                }
            }

            // 检查同九宫格是否有重复数字
            int startRow = row - row % 3;
            int startCol = col - col % 3;
            for (int i = 0; i < 3; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    if (board[startRow + i, startCol + j].Number == num)
                    {
                        return false;
                    }
                }
            }

            return true; // 没有重复数字
        }
    }

}
